{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Transform to Chessboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: movesToChessboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #变为棋盘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个&nbsp;<code>n x n</code>&nbsp;的二维网络&nbsp;<code>board</code>&nbsp;仅由&nbsp;<code>0</code>&nbsp;和&nbsp;<code>1</code>&nbsp;组成&nbsp;。每次移动，你能任意交换两列或是两行的位置。</p>\n",
    "\n",
    "<p>返回 <em>将这个矩阵变为<strong>&nbsp; “棋盘”&nbsp;&nbsp;</strong>所需的最小移动次数&nbsp;</em>。如果不存在可行的变换，输出 <code>-1</code>。</p>\n",
    "\n",
    "<p><strong>“棋盘”</strong> 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/chessboard1-grid.jpg\" style=\"height: 145px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>一种可行的变换方式如下，从左到右：\n",
    "第一次移动交换了第一列和第二列。\n",
    "第二次移动交换了第二行和第三行。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/chessboard2-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> board = [[0, 1], [1, 0]]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释: </strong>注意左上角的格值为0时也是合法的棋盘，也是合法的棋盘.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/06/29/chessboard3-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> board = [[1, 0], [1, 0]]\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释: </strong>任意的变换都不能使这个输入变为合法的棋盘。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == board.length</code></li>\n",
    "\t<li><code>n == board[i].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 30</code></li>\n",
    "\t<li><code>board[i][j]</code>&nbsp;将只包含&nbsp;<code>0</code>或&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [transform-to-chessboard](https://leetcode.cn/problems/transform-to-chessboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [transform-to-chessboard](https://leetcode.cn/problems/transform-to-chessboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]', '[[0,1],[1,0]]', '[[1,0],[1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        # 棋盘的第一行与第一列\n",
    "        rowMask = colMask = 0\n",
    "        for i in range(n):\n",
    "            rowMask |= board[0][i] << i\n",
    "            colMask |= board[i][0] << i\n",
    "        reverseRowMask = ((1 << n) - 1) ^ rowMask\n",
    "        reverseColMask = ((1 << n) - 1) ^ colMask\n",
    "        rowCnt = colCnt = 0\n",
    "        for i in range(n):\n",
    "            currRowMask = currColMask = 0\n",
    "            for j in range(n):\n",
    "                currRowMask |= board[i][j] << j\n",
    "                currColMask |= board[j][i] << j\n",
    "            # 检测每一行和每一列的状态是否合法\n",
    "            if currRowMask != rowMask and currRowMask != reverseRowMask or \\\n",
    "               currColMask != colMask and currColMask != reverseColMask:\n",
    "                return -1\n",
    "            rowCnt += currRowMask == rowMask  # 记录与第一行相同的行数\n",
    "            colCnt += currColMask == colMask  # 记录与第一列相同的列数\n",
    "\n",
    "        def getMoves(mask: int, count: int) -> int:\n",
    "            ones = mask.bit_count()\n",
    "            if n & 1:\n",
    "                # 如果 n 为奇数，则每一行中 1 与 0 的数目相差为 1，且满足相邻行交替\n",
    "                if abs(n - 2 * ones) != 1 or abs(n - 2 * count) != 1:\n",
    "                    return -1\n",
    "                if ones == n // 2:\n",
    "                    # 偶数位变为 1 的最小交换次数\n",
    "                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                else:\n",
    "                    # 奇数位变为 1 的最小交换次数\n",
    "                    return (n + 1) // 2 - (mask & 0x55555555).bit_count()\n",
    "            else:\n",
    "                # 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替\n",
    "                if ones != n // 2 or count != n // 2:\n",
    "                    return -1\n",
    "                # 偶数位变为 1 的最小交换次数\n",
    "                count0 = n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                # 奇数位变为 1 的最小交换次数\n",
    "                count1 = n // 2 - (mask & 0x55555555).bit_count()\n",
    "                return min(count0, count1)\n",
    "\n",
    "        rowMoves = getMoves(rowMask, rowCnt)\n",
    "        colMoves = getMoves(colMask, colCnt)\n",
    "        return -1 if rowMoves == -1 or colMoves == -1 else rowMoves + colMoves\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        # 棋盘的第一行与第一列\n",
    "        rowMask = colMask = 0\n",
    "        for i in range(n):\n",
    "            rowMask |= board[0][i] << i\n",
    "            colMask |= board[i][0] << i\n",
    "        reverseRowMask = ((1 << n) - 1) ^ rowMask\n",
    "        reverseColMask = ((1 << n) - 1) ^ colMask\n",
    "        rowCnt = colCnt = 0\n",
    "        for i in range(n):\n",
    "            currRowMask = currColMask = 0\n",
    "            for j in range(n):\n",
    "                currRowMask |= board[i][j] << j\n",
    "                currColMask |= board[j][i] << j\n",
    "            # 检测每一行和每一列的状态是否合法\n",
    "            if currRowMask != rowMask and currRowMask != reverseRowMask or \\\n",
    "               currColMask != colMask and currColMask != reverseColMask:\n",
    "                return -1\n",
    "            rowCnt += currRowMask == rowMask  # 记录与第一行相同的行数\n",
    "            colCnt += currColMask == colMask  # 记录与第一列相同的列数\n",
    "\n",
    "        def getMoves(mask: int, count: int) -> int:\n",
    "            ones = mask.bit_count()\n",
    "            if n & 1:\n",
    "                # 如果 n 为奇数，则每一行中 1 与 0 的数目相差为 1，且满足相邻行交替\n",
    "                if abs(n - 2 * ones) != 1 or abs(n - 2 * count) != 1:\n",
    "                    return -1\n",
    "                if ones == n // 2:\n",
    "                    # 偶数位变为 1 的最小交换次数\n",
    "                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                else:\n",
    "                    # 奇数位变为 1 的最小交换次数\n",
    "                    return (n + 1) // 2 - (mask & 0x55555555).bit_count()\n",
    "            else:\n",
    "                # 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替\n",
    "                if ones != n // 2 or count != n // 2:\n",
    "                    return -1\n",
    "                # 偶数位变为 1 的最小交换次数\n",
    "                count0 = n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                # 奇数位变为 1 的最小交换次数\n",
    "                count1 = n // 2 - (mask & 0x55555555).bit_count()\n",
    "                return min(count0, count1)\n",
    "\n",
    "        rowMoves = getMoves(rowMask, rowCnt)\n",
    "        colMoves = getMoves(colMask, colCnt)\n",
    "        return -1 if rowMoves == -1 or colMoves == -1 else rowMoves + colMoves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        dic = Counter([tuple(row) for row in board])\n",
    "        rows = list(dic.keys())\n",
    "        if len(rows) != 2 or any(a == b for a, b in zip(rows[0], rows[1])) or abs(dic[rows[0]] - dic[rows[1]]) > 1 or abs(rows[0].count(0) - rows[0].count(1)) > 1:\n",
    "            return - 1\n",
    "        nrow = sum(board[0][i] != i % 2 for i in range(n))\n",
    "        ncol = sum(board[i][0] != i % 2 for i in range(n))\n",
    "        nrow = n - nrow if nrow % 2 or n % 2 == 0 and n - nrow < nrow else nrow\n",
    "        ncol = n - ncol if ncol % 2 or n % 2 == 0 and n - ncol < ncol else ncol\n",
    "        return nrow // 2 + ncol // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\r\n",
    "        n=len(board)\r\n",
    "        row_mask=0\r\n",
    "        col_mask=0\r\n",
    "        for i in range(n):\r\n",
    "            row_mask|=board[0][i]<<i\r\n",
    "            col_mask|=board[i][0]<<i\r\n",
    "        r_row_mask=((1<<n)-1)^row_mask\r\n",
    "        r_col_mask=((1<<n)-1)^col_mask\r\n",
    "\r\n",
    "        row_cnt=col_cnt=0\r\n",
    "        for r in range(n):\r\n",
    "            cur_row_mask=cur_col_mask=0\r\n",
    "            for c in range(n):\r\n",
    "                cur_row_mask|=board[r][c]<<c\r\n",
    "                cur_col_mask|=board[c][r]<<c\r\n",
    "            if (cur_col_mask!=col_mask and cur_col_mask!=r_col_mask) or (cur_row_mask!=row_mask and cur_row_mask!=r_row_mask):\r\n",
    "                return -1\r\n",
    "            if cur_col_mask==col_mask:\r\n",
    "                col_cnt+=1\r\n",
    "            if cur_row_mask==row_mask:\r\n",
    "                row_cnt+=1\r\n",
    "\r\n",
    "        if abs(n-2*row_cnt)>1 or abs(n-2*col_cnt)>1:\r\n",
    "            return -1\r\n",
    "        \r\n",
    "        odd_mask=0x55555555#0101\r\n",
    "        even_mask=0xAAAAAAAA#1010\r\n",
    "        def get_moves(mask:int):\r\n",
    "            nonlocal n\r\n",
    "            ones=mask.bit_count()\r\n",
    "            if abs(n-2*ones)>1:\r\n",
    "                return -1\r\n",
    "            if n&1:\r\n",
    "                if ones==n//2:\r\n",
    "                    return ones-(mask&even_mask).bit_count()\r\n",
    "                else:\r\n",
    "                    return ones-(mask&odd_mask).bit_count()\r\n",
    "            else:\r\n",
    "                return ones-max((mask&odd_mask).bit_count(),(mask&even_mask).bit_count())\r\n",
    "        \r\n",
    "        c1=get_moves(row_mask)\r\n",
    "        if c1==-1:\r\n",
    "            return -1\r\n",
    "        c2=get_moves(col_mask)\r\n",
    "        if c2==-1:\r\n",
    "            return -1\r\n",
    "        return c1+c2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        # 棋盘的第一行与第一列\n",
    "        rowMask = colMask = 0\n",
    "        for i in range(n):\n",
    "            rowMask |= board[0][i] << i\n",
    "            colMask |= board[i][0] << i\n",
    "        reverseRowMask = ((1 << n) - 1) ^ rowMask\n",
    "        reverseColMask = ((1 << n) - 1) ^ colMask\n",
    "        rowCnt = colCnt = 0\n",
    "        for i in range(n):\n",
    "            currRowMask = currColMask = 0\n",
    "            for j in range(n):\n",
    "                currRowMask |= board[i][j] << j\n",
    "                currColMask |= board[j][i] << j\n",
    "            # 检测每一行和每一列的状态是否合法\n",
    "            if currRowMask != rowMask and currRowMask != reverseRowMask or \\\n",
    "               currColMask != colMask and currColMask != reverseColMask:\n",
    "                return -1\n",
    "            rowCnt += currRowMask == rowMask  # 记录与第一行相同的行数\n",
    "            colCnt += currColMask == colMask  # 记录与第一列相同的列数\n",
    "\n",
    "        def getMoves(mask: int, count: int) -> int:\n",
    "            ones = mask.bit_count()\n",
    "            if n & 1:\n",
    "                # 如果 n 为奇数，则每一行中 1 与 0 的数目相差为 1，且满足相邻行交替\n",
    "                if abs(n - 2 * ones) != 1 or abs(n - 2 * count) != 1:\n",
    "                    return -1\n",
    "                if ones == n // 2:\n",
    "                    # 偶数位变为 1 的最小交换次数\n",
    "                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                else:\n",
    "                    # 奇数位变为 1 的最小交换次数\n",
    "                    return (n + 1) // 2 - (mask & 0x55555555).bit_count()\n",
    "            else:\n",
    "                # 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替\n",
    "                if ones != n // 2 or count != n // 2:\n",
    "                    return -1\n",
    "                # 偶数位变为 1 的最小交换次数\n",
    "                count0 = n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                # 奇数位变为 1 的最小交换次数\n",
    "                count1 = n // 2 - (mask & 0x55555555).bit_count()\n",
    "                return min(count0, count1)\n",
    "\n",
    "        rowMoves = getMoves(rowMask, rowCnt)\n",
    "        colMoves = getMoves(colMask, colCnt)\n",
    "        return -1 if rowMoves == -1 or colMoves == -1 else rowMoves + colMoves\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        # 棋盘的第一行与第一列\n",
    "        rowMask = colMask = 0\n",
    "        for i in range(n):\n",
    "            rowMask |= board[0][i] << i\n",
    "            colMask |= board[i][0] << i\n",
    "        reverseRowMask = ((1 << n) - 1) ^ rowMask\n",
    "        reverseColMask = ((1 << n) - 1) ^ colMask\n",
    "        rowCnt = colCnt = 0\n",
    "        for i in range(n):\n",
    "            currRowMask = currColMask = 0\n",
    "            for j in range(n):\n",
    "                currRowMask |= board[i][j] << j\n",
    "                currColMask |= board[j][i] << j\n",
    "            # 检测每一行和每一列的状态是否合法\n",
    "            if currRowMask != rowMask and currRowMask != reverseRowMask or \\\n",
    "               currColMask != colMask and currColMask != reverseColMask:\n",
    "                return -1\n",
    "            rowCnt += currRowMask == rowMask  # 记录与第一行相同的行数\n",
    "            colCnt += currColMask == colMask  # 记录与第一列相同的列数\n",
    "\n",
    "        def getMoves(mask: int, count: int) -> int:\n",
    "            ones = mask.bit_count()\n",
    "            if n & 1:\n",
    "                # 如果 n 为奇数，则每一行中 1 与 0 的数目相差为 1，且满足相邻行交替\n",
    "                if abs(n - 2 * ones) != 1 or abs(n - 2 * count) != 1:\n",
    "                    return -1\n",
    "                if ones == n // 2:\n",
    "                    # 偶数位变为 1 的最小交换次数\n",
    "                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                else:\n",
    "                    # 奇数位变为 1 的最小交换次数\n",
    "                    return (n + 1) // 2 - (mask & 0x55555555).bit_count()\n",
    "            else:\n",
    "                # 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替\n",
    "                if ones != n // 2 or count != n // 2:\n",
    "                    return -1\n",
    "                # 偶数位变为 1 的最小交换次数\n",
    "                count0 = n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                # 奇数位变为 1 的最小交换次数\n",
    "                count1 = n // 2 - (mask & 0x55555555).bit_count()\n",
    "                return min(count0, count1)\n",
    "\n",
    "        rowMoves = getMoves(rowMask, rowCnt)\n",
    "        colMoves = getMoves(colMask, colCnt)\n",
    "        return -1 if rowMoves == -1 or colMoves == -1 else rowMoves + colMoves\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        bit = [0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j]:\n",
    "                    bit[i] |= (1 << j)\n",
    "        res = 0\n",
    "\n",
    "        # 交换行\n",
    "        if n % 2:\n",
    "            flag = sum([bit[i].bit_count() for i in range(n)]) > n*n//2\n",
    "            wrong = [[] for _ in range(2)]\n",
    "            for i in range(n):\n",
    "                if (bit[i].bit_count() > n // 2) != flag:\n",
    "                    wrong[flag].append(i)\n",
    "                flag ^= True\n",
    "            if len(wrong[0]) != len(wrong[1]):\n",
    "                return -1\n",
    "            for i in range(len(wrong[0])):\n",
    "                bit[wrong[0][i]], bit[wrong[1][i]] = bit[wrong[1][i]], bit[wrong[0][i]]\n",
    "                res += 1\n",
    "        else:\n",
    "            flag = bit[0]%2 == 1\n",
    "            wrong = [[] for _ in range(2)]\n",
    "            for i in range(n):\n",
    "                if bit[i] % 2 != int(flag):\n",
    "                    wrong[flag].append(i)\n",
    "                flag ^= True\n",
    "            if len(wrong[0]) != len(wrong[1]):\n",
    "                return -1\n",
    "            for i in range(len(wrong[0])):\n",
    "                bit[wrong[0][i]], bit[wrong[1][i]] = bit[wrong[1][i]], bit[wrong[0][i]]\n",
    "                res += 1\n",
    "            res = min(res, n // 2 - res)\n",
    "        bit2 = [0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if bit[i] & (1 << j):\n",
    "                    bit2[j] |= (1 << i)\n",
    "\n",
    "        # 交换列\n",
    "        if n % 2:\n",
    "            flag = sum([bit2[i].bit_count() for i in range(n)]) > n*n//2\n",
    "            wrong = [[] for _ in range(2)]\n",
    "            for i in range(n):\n",
    "                if (bit2[i].bit_count() > n // 2) != flag:\n",
    "                    wrong[flag].append(i)\n",
    "                flag ^= True\n",
    "            if len(wrong[0]) != len(wrong[1]):\n",
    "                return -1\n",
    "            for i in range(len(wrong[0])):\n",
    "                bit2[wrong[0][i]], bit2[wrong[1][i]] = bit2[wrong[1][i]], bit2[wrong[0][i]]\n",
    "                res += 1\n",
    "        else:\n",
    "            res2 = 0\n",
    "            flag = bit2[0]%2 == 1\n",
    "            wrong = [[] for _ in range(2)]\n",
    "            for i in range(n):\n",
    "                if bit2[i] % 2 != int(flag):\n",
    "                    wrong[flag].append(i)\n",
    "                flag ^= True\n",
    "            if len(wrong[0]) != len(wrong[1]):\n",
    "                return -1\n",
    "            for i in range(len(wrong[0])):\n",
    "                bit2[wrong[0][i]], bit2[wrong[1][i]] = bit2[wrong[1][i]], bit2[wrong[0][i]]\n",
    "                res2 += 1\n",
    "            res2 = min(res2, n//2-res2)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for (x, y) in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                    if 0 <= x < n and 0 <= y < n:\n",
    "                        if bit2[x] & (1 << y) == bit2[i] & (1 << j):\n",
    "                            return -1\n",
    "        return res if n % 2 else res+res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        r,b=self.checkrow(board)\n",
    "        #print(b)\n",
    "        if r==-1:\n",
    "            return -1\n",
    "        res=r\n",
    "        for i in range(len(b)):\n",
    "            for j in range(i+1,len(b)):\n",
    "                c1=b[i][j]\n",
    "                c2=b[j][i]\n",
    "                b[i][j]=c2\n",
    "                b[j][i]=c1\n",
    "       \n",
    "        r,b=self.checkrow(b)\n",
    "        #print(b)\n",
    "        if r==-1:\n",
    "            return -1\n",
    "        return res+r\n",
    "    def checkrow(self,board):\n",
    "        zeros=0\n",
    "        ones=0\n",
    "        for i in range(len(board)):\n",
    "            if board[i][0]==0:\n",
    "                zeros+=1\n",
    "            else:\n",
    "                ones+=1\n",
    "        if abs(zeros-ones)>1:\n",
    "            return -1,board\n",
    "        exchange=0\n",
    "        if zeros>ones:\n",
    "            cur=0\n",
    "        if ones>zeros:\n",
    "            cur=1\n",
    "        if ones==zeros:\n",
    "            cur=board[0][0]\n",
    "        flag=[0 for i in range(len(board))]\n",
    "        tc=cur\n",
    "        for i in range(len(flag)):\n",
    "            flag[i]=tc\n",
    "            if tc==0:\n",
    "                tc=1\n",
    "            else:\n",
    "                tc=0\n",
    "        if ones==zeros:\n",
    "            right=0\n",
    "            for i in range(len(flag)):\n",
    "                if flag[i]==board[i][0]:\n",
    "                    right+=1\n",
    "            wrong=len(flag)-right\n",
    "            if wrong>right:\n",
    "                if cur==0:\n",
    "                    cur=1\n",
    "                else:\n",
    "                    cur=0\n",
    "                for i in range(1,len(flag)):\n",
    "                    flag[i],flag[i-1]=flag[i-1],flag[i]\n",
    "        for i in range(0,len(board)-1):\n",
    "            if board[i][0]!=cur:\n",
    "                exchange+=1\n",
    "                tag=True\n",
    "                for j in range(i+1,len(board)-1):\n",
    "                    if board[j][0]==cur and board[j+1][0]==cur:\n",
    "                        tag=False\n",
    "                        if board[j][0]==flag[j]:\n",
    "                            board[i],board[j+1]=board[j+1],board[i]\n",
    "                        else:\n",
    "                            board[i],board[j]=board[j],board[i]\n",
    "                        break\n",
    "                if tag:\n",
    "                    board[i],board[-1]=board[-1],board[i]\n",
    "            if cur==0:\n",
    "                cur=1\n",
    "            else:\n",
    "                cur=0\n",
    "\n",
    "\n",
    "        for i in range(1,len(board)):\n",
    "            for j in range(len(board)):\n",
    "                if board[i][j]==board[i-1][j]:\n",
    "                    return -1,board\n",
    "        return exchange,board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        # 棋盘的第一行与第一列\n",
    "        rowMask = colMask = 0\n",
    "        for i in range(n):\n",
    "            rowMask |= board[0][i] << i\n",
    "            colMask |= board[i][0] << i\n",
    "        reverseRowMask = ((1 << n) - 1) ^ rowMask\n",
    "        reverseColMask = ((1 << n) - 1) ^ colMask\n",
    "        rowCnt = colCnt = 0\n",
    "        for i in range(n):\n",
    "            currRowMask = currColMask = 0\n",
    "            for j in range(n):\n",
    "                currRowMask |= board[i][j] << j\n",
    "                currColMask |= board[j][i] << j\n",
    "            # 检测每一行和每一列的状态是否合法\n",
    "            if currRowMask != rowMask and currRowMask != reverseRowMask or \\\n",
    "               currColMask != colMask and currColMask != reverseColMask:\n",
    "                return -1\n",
    "            rowCnt += currRowMask == rowMask  # 记录与第一行相同的行数\n",
    "            colCnt += currColMask == colMask  # 记录与第一列相同的列数\n",
    "\n",
    "        def getMoves(mask: int, count: int) -> int:\n",
    "            ones = mask.bit_count()\n",
    "            if n & 1:\n",
    "                # 如果 n 为奇数，则每一行中 1 与 0 的数目相差为 1，且满足相邻行交替\n",
    "                if abs(n - 2 * ones) != 1 or abs(n - 2 * count) != 1:\n",
    "                    return -1\n",
    "                if ones == n // 2:\n",
    "                    # 偶数位变为 1 的最小交换次数\n",
    "                    return n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                else:\n",
    "                    # 奇数位变为 1 的最小交换次数\n",
    "                    return (n + 1) // 2 - (mask & 0x55555555).bit_count()\n",
    "            else:\n",
    "                # 如果 n 为偶数，则每一行中 1 与 0 的数目相等，且满足相邻行交替\n",
    "                if ones != n // 2 or count != n // 2:\n",
    "                    return -1\n",
    "                # 偶数位变为 1 的最小交换次数\n",
    "                count0 = n // 2 - (mask & 0xAAAAAAAA).bit_count()\n",
    "                # 奇数位变为 1 的最小交换次数\n",
    "                count1 = n // 2 - (mask & 0x55555555).bit_count()\n",
    "                return min(count0, count1)\n",
    "\n",
    "        rowMoves = getMoves(rowMask, rowCnt)\n",
    "        colMoves = getMoves(colMask, colCnt)\n",
    "        return -1 if rowMoves == -1 or colMoves == -1 else rowMoves + colMoves\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        def f(x):\n",
    "            c = Counter(tuple(r) for r in x)\n",
    "            if len(c) != 2:\n",
    "                return math.inf\n",
    "            r = list(c.keys())\n",
    "            if any(a == b for a,b in zip(r[0], r[1])):\n",
    "                return math.inf\n",
    "            p, q = c.values()\n",
    "            if abs(p-q) > 1:\n",
    "                return math.inf\n",
    "            ans1 = ans2 = 0\n",
    "            for i,s in enumerate(map(tuple, x)):\n",
    "                ans1 += (s != r[i%2])\n",
    "                ans2 += (s != r[(i+1)%2])\n",
    "            if ans1 % 2: ans1 = math.inf\n",
    "            if ans2 % 2: ans2 = math.inf\n",
    "            return min(ans1, ans2) // 2 \n",
    "        \n",
    "        ans = f(board) + f(list(zip(*board)))\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "\n",
    "        def f(L):\n",
    "            tmp = 0\n",
    "            for i in L:\n",
    "                tmp = tmp * 2 + i\n",
    "            return tmp\n",
    "\n",
    "        cnt1 = 0\n",
    "        for r in board:\n",
    "            cnt1 += sum(r)\n",
    "        if abs(2 * cnt1 - n ** 2) > 1:\n",
    "            return -1\n",
    "        if 2 * cnt1 - n ** 2 == -1:\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    board[i][j] = board[i][j] ^ 1\n",
    "\n",
    "        def judge(grid):\n",
    "            cnt_row = Counter()\n",
    "            for r in grid:\n",
    "                cnt_row[f(r)] += 1\n",
    "            if len(cnt_row) != 2:\n",
    "                return False\n",
    "            v1, v2 = cnt_row.keys()\n",
    "            if (v1 ^ v2) != (1 << n) - 1:\n",
    "                return False\n",
    "            for v in [v1, v2]:\n",
    "                if abs(v.bit_count() * 2 - n) > 1:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        if not judge(board) or not judge(list(zip(*board))):\n",
    "            return -1\n",
    "        one = int('10' * (n // 2) + (n % 2) * '1', 2)\n",
    "        zero = ((1 << n) - 1) ^ one\n",
    "        ans = inf\n",
    "        cnt_row = Counter()\n",
    "        for r in board:\n",
    "            cnt_row[f(r)] += 1\n",
    "        cnt_col = Counter()\n",
    "        for col in list(zip(*board)):\n",
    "            cnt_col[f(col)] += 1\n",
    "        if n % 2:\n",
    "            row_max, row_min = list(cnt_row.keys())\n",
    "            if row_max.bit_count() < row_min.bit_count():\n",
    "                row_max, row_min = row_min, row_max\n",
    "            col_max, col_min = list(cnt_col.keys())\n",
    "            if col_max.bit_count() < col_min.bit_count():\n",
    "                col_max, col_min = col_min, col_max\n",
    "            ans = ((row_max ^ one).bit_count() + (col_max ^ one).bit_count()) // 2\n",
    "        else:\n",
    "            for tar in [zero, one]:\n",
    "                for i in list(cnt_row.keys()):\n",
    "                    for j in list(cnt_col.keys()):\n",
    "                        ans = min(ans, ((tar ^ i).bit_count() + (tar ^ j).bit_count()) // 2)\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        if not self.assert1():\n",
    "            return -1\n",
    "        if not self.assert2():\n",
    "            return -1 \n",
    "        return self.num_hori() + self.num_vert()\n",
    "    def num_hori(self):\n",
    "        lst = self.board[0,:]\n",
    "        len1 = len(lst)\n",
    "        if len1 % 2 == 0:\n",
    "            nn=[0,0]\n",
    "            for i in range(0,len1, 2):\n",
    "                f2 = lst[i]\n",
    "                nn[f2] += 1\n",
    "            return min(nn)\n",
    "        n1 = len(lst[lst>0])\n",
    "        n0 = len1 - n1\n",
    "        v = int(n1 > n0)\n",
    "        sum1 = 0\n",
    "        for i in range(1, len1, 2):\n",
    "            if lst[i] == v:\n",
    "                sum1 += 1\n",
    "        return sum1\n",
    "\n",
    "    def num_vert(self):\n",
    "        lst = self.board[:,0]\n",
    "        len1 = len(lst)\n",
    "        if len1 % 2 == 0:\n",
    "            nn=[0,0]\n",
    "            for i in range(0,len1, 2):\n",
    "                f2 = lst[i]\n",
    "                nn[f2] += 1\n",
    "            return min(nn)\n",
    "        n1 = len(lst[lst>0])\n",
    "        n0 = len1 - n1\n",
    "        v = int(n1 > n0)\n",
    "        sum1 = 0\n",
    "        for i in range(1, len1, 2):\n",
    "            if lst[i] == v:\n",
    "                sum1 += 1\n",
    "        return sum1\n",
    "\n",
    "    def assert1(self):\n",
    "        width,height=self.board.shape\n",
    "        lst = self.board[0,:]\n",
    "        len1 = len(lst)\n",
    "        n1 = len(lst[lst>0])\n",
    "        n2 = len1 - n1\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        for i in range(1,height):\n",
    "            if np.array_equal(lst, self.board[i,:]):\n",
    "                continue\n",
    "            if np.array_equal(lst, 1-self.board[i,:]):\n",
    "                continue\n",
    "            return False\n",
    "        return True\n",
    "    def assert2(self):\n",
    "        width,height=self.board.shape\n",
    "        lst = self.board[:,0]\n",
    "        len1 = len(lst)\n",
    "        n1 = len(lst[lst>0])\n",
    "        n2 = len1 - n1\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        for i in range(1, width):\n",
    "            if np.array_equal(lst, self.board[:,i]):\n",
    "                continue\n",
    "            if np.array_equal(lst, 1-self.board[:,i]):\n",
    "                continue\n",
    "            return False\n",
    "        return True        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # 判断第一行1和0的个数\n",
    "    def func1(self):\n",
    "        lst1 = self.board[0,:]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断第一列1和0的个数\n",
    "    def func2(self):\n",
    "        lst1 = self.board[:,0]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断每一行与第一行是否相同或是相差1\n",
    "    def func3(self):\n",
    "        n = len(self.board)\n",
    "        for i in range(1,n):\n",
    "            lst1 = self.board[0,:]           \n",
    "            lst2 = self.board[i,:]\n",
    "            if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "                return False\n",
    "        return True\n",
    "    # 判断每一列与第一列是否相同或是相差1\n",
    "    def func4(self):\n",
    "        n = len(self.board)\n",
    "        for i in range(1,n):\n",
    "            lst1 = self.board[:,0]           \n",
    "            lst2 = self.board[:,i]\n",
    "            if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    # 分奇偶讨论第一行要移动几位\n",
    "    def func5(self):\n",
    "        lst = self.board[0, :]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res)-nums1\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst)-nums3\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1\n",
    "    # 分奇偶讨论第一列要移动几位 \n",
    "    def func6(self):\n",
    "        lst = self.board[:, 0]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res)-nums1\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst)-nums3\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1 \n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        n = len(self.board)\n",
    "        if not self.func1():\n",
    "            return -1\n",
    "        if not self.func2():\n",
    "            return -1\n",
    "        if not self.func3():\n",
    "            return -1\n",
    "        if not self.func4():\n",
    "            return -1\n",
    "        return self.func5()+self.func6()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # 判断第一行1和0的个数\n",
    "    def func1(self):\n",
    "        lst1 = self.board[0,:]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断第一列1和0的个数\n",
    "    def func2(self):\n",
    "        lst1 = self.board[:,0]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断每一行与上一行是否相同或是相差1\n",
    "    def func3(self,i):\n",
    "        n = len(self.board)\n",
    "        lst1 = self.board[i-1, :]\n",
    "        lst3 = self.board[:,i-1]\n",
    "        \n",
    "        lst2 = self.board[i,:]\n",
    "        lst4 = self.board[:,i]\n",
    "        if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "            return False\n",
    "        elif not np.array_equal(lst4,lst3) and not np.array_equal(lst4,1-lst3):\n",
    "            return False\n",
    "        return True\n",
    "    # 分奇偶讨论第一行要移动几位\n",
    "    def func4(self):\n",
    "        lst = self.board[0, :]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1\n",
    "    # 分奇偶讨论第一列要移动几位 \n",
    "    def func5(self):\n",
    "        lst = self.board[:, 0]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1 \n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        n = len(self.board)\n",
    "        if not self.func1():\n",
    "            return -1\n",
    "        if not self.func2():\n",
    "            return -1\n",
    "        for i in range(1,n):\n",
    "            if not self.func3(i):\n",
    "                return -1\n",
    "        return self.func4()+self.func5()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def func2(self,i):\n",
    "        lst1 = self.board[i,:]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        lst2 = self.board[:,i]\n",
    "        n3 = len(lst2[lst2 > 0])\n",
    "        n4 = len(lst2[lst2 < 1])\n",
    "        if abs(n1-n2) > 1 or abs(n3-n4) > 1:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def func3(self,i):\n",
    "        n = len(self.board)\n",
    "        lst1 = self.board[i-1, :]\n",
    "        lst3 = self.board[:,i-1]\n",
    "        \n",
    "        lst2 = self.board[i,:]\n",
    "        lst4 = self.board[:,i]\n",
    "        if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "            return False\n",
    "        elif not np.array_equal(lst4,lst3) and not np.array_equal(lst4,1-lst3):\n",
    "            return False\n",
    "        return True\n",
    "    def func4(self):\n",
    "        lst = self.board[0, :]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1\n",
    "    def func5(self):\n",
    "        lst = self.board[:, 0]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1 \n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        n = len(self.board)\n",
    "        for i in range(n):\n",
    "            if not self.func2(i):\n",
    "                return -1\n",
    "        for i in range(1,n):\n",
    "            if not self.func3(i):\n",
    "                return -1\n",
    "        return self.func4()+self.func5()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # 判断每行每列1和0的个数\n",
    "    def func2(self,i):\n",
    "        lst1 = self.board[i,:]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        lst2 = self.board[:,i]\n",
    "        n3 = len(lst2[lst2 > 0])\n",
    "        n4 = len(lst2[lst2 < 1])\n",
    "        if abs(n1-n2) > 1 or abs(n3-n4) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断每一行与上一行是否相同或是相差1\n",
    "    def func3(self,i):\n",
    "        n = len(self.board)\n",
    "        lst1 = self.board[i-1, :]\n",
    "        lst3 = self.board[:,i-1]\n",
    "        \n",
    "        lst2 = self.board[i,:]\n",
    "        lst4 = self.board[:,i]\n",
    "        if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "            return False\n",
    "        elif not np.array_equal(lst4,lst3) and not np.array_equal(lst4,1-lst3):\n",
    "            return False\n",
    "        return True\n",
    "    # 分奇偶讨论第一行要移动几位\n",
    "    def func4(self):\n",
    "        lst = self.board[0, :]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1\n",
    "    # 分奇偶讨论第一列要移动几位 \n",
    "    def func5(self):\n",
    "        lst = self.board[:, 0]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1 \n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        n = len(self.board)\n",
    "        for i in range(n):\n",
    "            if not self.func2(i):\n",
    "                return -1\n",
    "        for i in range(1,n):\n",
    "            if not self.func3(i):\n",
    "                return -1\n",
    "        return self.func4()+self.func5()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # 判断第一行1和0的个数\n",
    "    def func1(self):\n",
    "        lst1 = self.board[0,:]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1)-n1\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断第一列1和0的个数\n",
    "    def func2(self):\n",
    "        lst1 = self.board[:,0]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1)-n1\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断每一行与第一行是否相同或是相差1\n",
    "    def func3(self):\n",
    "        n = len(self.board)\n",
    "        lst1 = self.board[0,:]  \n",
    "        for i in range(1,n):         \n",
    "            lst2 = self.board[i,:]\n",
    "            if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "                return False\n",
    "        return True\n",
    "    # 判断每一列与第一列是否相同或是相差1\n",
    "    def func4(self):\n",
    "        n = len(self.board)\n",
    "        lst1 = self.board[:,0] \n",
    "        for i in range(1,n):   \n",
    "            lst2 = self.board[:,i]\n",
    "            if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    # 分奇偶讨论第一行要移动几位\n",
    "    def func5(self):\n",
    "        lst = self.board[0, :]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res)-nums1\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst)-nums3\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1\n",
    "    # 分奇偶讨论第一列要移动几位 \n",
    "    def func6(self):\n",
    "        lst = self.board[:, 0]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res)-nums1\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst)-nums3\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1 \n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        n = len(self.board)\n",
    "        if not self.func1():\n",
    "            return -1\n",
    "        if not self.func2():\n",
    "            return -1\n",
    "        if not self.func3():\n",
    "            return -1\n",
    "        if not self.func4():\n",
    "            return -1\n",
    "        return self.func5()+self.func6()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    # 判断第一行1和0的个数\n",
    "    def func1(self):\n",
    "        lst1 = self.board[0,:]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断第一列1和0的个数\n",
    "    def func2(self):\n",
    "        lst1 = self.board[:,0]\n",
    "        n1 = len(lst1[lst1 > 0])\n",
    "        n2 = len(lst1[lst1 < 1])\n",
    "        if abs(n1-n2) > 1:\n",
    "            return False\n",
    "        return True\n",
    "    # 判断每一行与上一行是否相同或是相差1\n",
    "    def func3(self):\n",
    "        n = len(self.board)\n",
    "        for i in range(1,n):\n",
    "            lst1 = self.board[i-1, :]           \n",
    "            lst2 = self.board[i,:]\n",
    "            if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "                return False\n",
    "        return True\n",
    "    # 判断每一列与上一列是否相同或是相差1\n",
    "    def func4(self):\n",
    "        n = len(self.board)\n",
    "        for i in range(1,n):\n",
    "            lst1 = self.board[:, i-1]           \n",
    "            lst2 = self.board[:,i]\n",
    "            if not np.array_equal(lst2,lst1) and not np.array_equal(lst2,1-lst1):\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    # 分奇偶讨论第一行要移动几位\n",
    "    def func5(self):\n",
    "        lst = self.board[0, :]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1\n",
    "    # 分奇偶讨论第一列要移动几位 \n",
    "    def func6(self):\n",
    "        lst = self.board[:, 0]\n",
    "        n = len(lst)\n",
    "        res = []\n",
    "        for i in range(0,n,2):\n",
    "            res.append(lst[i])\n",
    "        res = np.array(res)\n",
    "        nums1 = len(res[res > 0])\n",
    "        nums2 = len(res[res < 1])\n",
    "        if n % 2 == 0:\n",
    "            return min(nums1,nums2)\n",
    "        nums3 = len(lst[lst > 0])\n",
    "        nums4 = len(lst[lst < 1])\n",
    "        if nums3 > nums4:\n",
    "            return nums3-nums1\n",
    "        return nums1 \n",
    "    def movesToChessboard(self, board: List[List[int]]) -> int:\n",
    "        self.board = np.array(board)\n",
    "        n = len(self.board)\n",
    "        if not self.func1():\n",
    "            return -1\n",
    "        if not self.func2():\n",
    "            return -1\n",
    "        if not self.func3():\n",
    "            return -1\n",
    "        if not self.func4():\n",
    "            return -1\n",
    "        return self.func5()+self.func6()"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
